from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        """将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 """
        # 递归必须有终止条件
        if not list1:
            return list2
        if not list2:
            return list1

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。"""
        cur_node = head
        while cur_node and cur_node.next:
            if cur_node.val == cur_node.next.val:
                cur_node.next = cur_node.next.next
            else:
                cur_node = cur_node.next
        return head

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        """给你一个链表的头节点 head ，判断链表中是否有环。"""
        # todo 快慢指针,暂时没理解为什么不存在跳过情况
        pass



if __name__ == '__main__':
    s = Solution()

    # list1 = ListNode(1, ListNode(2, ListNode(4)))
    # list2 = ListNode(1, ListNode(3, ListNode(4)))
    # merge_link = s.mergeTwoLists(list1, list2)
    # print(merge_link)

    # head = ListNode(1, ListNode(1, ListNode(2, ListNode(3, ListNode(3)))))
    # delete_duplicate_link = s.deleteDuplicates(head)
    # print(delete_duplicate_link)

    head = ListNode(3, ListNode(2, ListNode(0, ListNode(4))))
    head.next.next.next.next = head.next
    hasCycle_link = s.hasCycle(head)
    print(hasCycle_link)
